package leetcode.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 n皇后问题 研究的是如何将 n个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

 给你一个整数 n ，返回所有不同的n皇后问题 的解决方案。

 每一种解法包含一个不同的n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

 */
public class NQueens {

    public static void main(String[] args) {
        List<List<String>> lists = new NQueens().solveNQueens(5);
        for (List<String> list : lists) {
            for (String s : list) {
                System.out.print(s+" ");
            }
            System.out.println();
        }
    }
    public List<List<String>> solveNQueens(int n) {
        //board为一个解
        List<List<String>> res = new ArrayList<List<String>>();
        boolean []ldiag = new boolean[2*n];//左对角线，n-row+col的值为恒定值，【1,2n-1】
        boolean []rdiag = new boolean[2*n];//右对角线，row+col的值为恒定值，【0,2n-2】
        boolean []col = new boolean[n];
        char[][] board= new char[n][n];
        for (char[] chars : board) {
            Arrays.fill(chars, '.');
        }
        find(res,board,0,n,col,ldiag,rdiag);

        return res;
    }

    private void find(List<List<String>> res,char[][] board,//解
                      int row,int n,//访问参数 row：当前所在行数
                      boolean []col,boolean []ldiag,boolean []rdiag){//访问状态

        if(row==n){//这就是一个解了
            ArrayList<String> list = new ArrayList<>();
            for (char[] chars : board) {//一个解
                StringBuilder str = new StringBuilder();
                for (char aChar : chars) {
                    str.append(aChar);
                }
                list.add(str.toString());//一行
            }
            res.add(list);
            return;
        }

        for (int i = 0; i < n; i++) {//对row这一行，开始遍历所有列，看看能不能放

            if(col[i] || ldiag[n-row+i] || rdiag[i+row])
                continue;

            board[row][i] = 'Q'; //修改状态
            ldiag[n-row+i] = true;
            rdiag[i+row] = true;
            col[i] = true;//这一列已经放了

            find(res,board,row+1,n,col,ldiag,rdiag);//在这列，看看下一行能不能继续

            board[row][i] = '.';//回改状态
            ldiag[n-row+i] = false;
            rdiag[i+row] = false;
            col[i] = false;
        }
    }
}